package com.atcumt.Carl.LinkedList;

public class LinkedList02 {

    /**
     * 排序链表
     * 利用归并的思想，递归地将当前链表分为两段，然后merge，分两段的方法是使用 fast-slow 法，
     * 用两个指针，一个每次走两步，一个走一步，知道快的走到了末尾，然后慢的所在位置就是中间位置，这样就分成了两段。
     * merge时，把两段头部节点值比较，用一个 p 指向较小的，且记录第一个节点，然后两段的头一步一步向后走，p也一直向后走，
     * 总是指向较小节点，直至其中一个头为 NULL，处理剩下的元素。最后返回记录的头即可。
     */
    public ListNode sortList(ListNode head) {
        // 递归结束
        if (head == null || head.next == null) {
            return head;
        }

        // 将当前链表分为两段，然后merge
        ListNode midNode = fineMidNode(head);
        ListNode rightHead = midNode.next;
        midNode.next = null;

        ListNode left = sortList(head);
        ListNode right = sortList(rightHead);

        return merge(left, right);

    }

    private ListNode fineMidNode(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    private ListNode merge(ListNode left, ListNode right) {
        ListNode dummyHead = new ListNode(-1);
        ListNode cur = dummyHead;

        while (left != null && right != null) {
            if (left.val < right.val) {
                cur.next = left;
                left = left.next;
            } else {
                cur.next = right;
                right = right.next;
            }
            cur = cur.next;
        }
        cur.next = left != null ? left : right;
        return dummyHead.next;
    }

}
